package com.wubotao.algorithm;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Shell {

	public static <E extends Comparable<? super E>> void sort(List<E> list) {
		int h = 1;
		while (h < list.size() / 3) {
			h = h * 3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
		}

		for (; h >= 1; h /= 3) {
			for (int i = h; i < list.size(); i++) {
				for (int j = i; j >= h
						&& list.get(j).compareTo(list.get(j - h)) < 0; j -= h) {
					Collections.swap(list, j, j - h);
				}
			}
		}
	}

	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(5, 69, 12, 3, 56, 789, 2, 5648, 23);
		sort(list);
		System.out.println(list);
	}

}


